package org.korifey.ffalg;

import java.util.Comparator;

public class Sorts {

	private static void swap(int[] a, int i, int j) {
		int s = a[i];
		a[i] = a[j];
		a[j] = s;
	}

	public static void insertionSort(int[] a) {
		insertionSort(a, 0, a.length - 1);
	}

	public static void insertionSort(int[] a, int start, int finish) {
		for (int i = start + 1; i <= finish; i++) {
			for (int j = i - 1; j >= start; j--) {
				if (a[j] > a[j + 1])
					swap(a, j, j + 1);
				else
					break;
			}
		}
	}

	public static void mergeSort(int[] a) {
		int[] tmpMemory = new int[a.length];
		mergeSort(a, 0, a.length - 1, tmpMemory);
	}

	public static void mergeSort(int[] a, int start, int finish, int[] tmpMemory) {
		if (start >= finish)
			return;

		int mid = (start + finish) / 2;
		mergeSort(a, start, mid, tmpMemory);
		mergeSort(a, mid + 1, finish, tmpMemory);

		int i = start, j = mid + 1, cur = 0;
		while (i <= mid && j <= finish) {
			if (a[i] < a[j]) {
				tmpMemory[cur++] = a[i++];
			} else {
				tmpMemory[cur++] = a[j++];
			}
		}
		if (i <= mid)
			System.arraycopy(a, i, tmpMemory, cur, mid - i + 1);
		if (j <= finish)
			System.arraycopy(a, j, tmpMemory, cur, finish - j + 1);
		
		System.arraycopy(tmpMemory, 0, a, start, finish - start + 1);

	}

	public static void quickSort(int[] a) {
		quickSort(a, 0, a.length - 1);
	}
	
	public static void quickSort(int[] a, int start, int finish) {
		if (start >= finish) return;
		
		int mid = a[(start + finish) / 2];

		int i = start, j = finish;
		while (i <= j) {
			while (a[i] < mid)
				i++;
			while (a[j] > mid)
				j--;
			if (i <= j) {
				swap(a, i, j);
				i++;
				j--;
			}
		}

		j = Math.max(j, start);
		quickSort(a, start, j);
		quickSort(a, j+1, finish);
	}
	
	public static int bsearch(int[] a, int x) {
		return bsearch(a, x, 0 , a.length - 1);
	}
	
	private static int bsearch(int[] a, int x, int start, int finish) {
		while (start < finish) {
			int m = (start + finish) >> 1;
			if (x > a[m]) start = m+1;
			else finish = m;
		}
		if (x == a[start]) return start;
		else if (x < a[start]) return -start - 1;
		else return -start - 2;
	}
	
	
	  private static void heapify(int [] a, int alen, int idx) {
		  assert idx >= 0;
		  assert idx < alen;
		  
		  while (true) {
			  int left = 2*idx + 1;
			  int right = 2*idx + 2;
			  int largest = idx;
			  if (left < alen && a[left] > a[largest]) largest = left;
			  if (right < alen && a[right] > a[largest]) largest = right;
			  			  
			  if (idx == largest) break;
			  swap(a, idx, largest);
			  idx = largest;			  
		  }
	  }	  
	  
	  public static void buildHeap(int[] a) {
		  for (int i=a.length / 2; i>=0; i--) {
			  heapify(a, a.length, i);
		  }
	  }
	  
	  public static void heapSort(int[] a) {
		  
		  buildHeap(a);
		  for (int len = a.length-1; len > 0; len --) {
			  swap(a,0,len);
			  heapify(a,  len, 0);
		  }
	  }
	
	
	public static class DefaultComparator<T> implements Comparator<T> {				
		@Override
		public int compare(T o1, T o2) {
			if (o1 == null) {
				if (o2 == null) return 0;
				else return -1;
			}
			if (o2 == null) {
				return 1;
			}
			if (o1 instanceof Comparable) {
				return ((Comparable) o1).compareTo(o2);
			}		
			return 0;
		}		
	}
	
	public static class InverseComparator<T> implements Comparator<T> {

		private Comparator<T> directComparator;
		
				
		public InverseComparator(Comparator<T> directComparator) {
			super();
			this.directComparator = directComparator;
		}



		@Override
		public int compare(T o1, T o2) {			
			return -directComparator.compare(o1, o2);
		}
		
	}
	
	public static class ZeroComparator<T> implements Comparator<T> {

		@Override
		public int compare(T o1, T o2) {			
			return 0;
		}		
	}
}
